This invention relates generally to a method and apparatus for data compression and, in particular, to a novel method and apparatus for reducing the number of bits of information needed to transmit a video image using a non-adaptive prediction technique.
In the transmission of digital data, it is desirable to reduce the amount of data to be transmitted as much as possible in order to reduce the bandwidth requirements of transmission medium and storage requirements. One technique which has proven useful is run length encoding. This particular technique consists of partitioning each row of the image into a sequence of runs, with each run including one or more adjacent picture elements, called pixels or pels, with the same binary value, and representing each run with a symbol or code which specifies the length of the run. Often these runs are represented by variable-length codes, such as a Huffman code set, and are assigned such that the shorter code words are used to represent the symbols which are more likely to occur, and the longer code words stand for symbols which rarely appear.
When the image data to be transmitted exhibits a high degree of redundancy, it has been shown that predictive encoding further improves the compression ratio. Predictive encoding is a technique by which a prediction may be made as to the value of a particular bit being processed based upon information gathered by examining surrounding data bits (pixels). The common method of predictive encoding is known as adaptive prediction. Examples of several prediction techniques may be found in U.S. Pat. No. 3,769,453 issued Oct. 30, 1973, to L. R. Bahl et al.; U.S. Pat. No. 4,093,962 issued June 6, 1978 to P. Ishiguro et al; and U.S. Pat. No. 4,215,375 issued July 29, 1980 to T. Usubuchi et al. When using adaptive prediction, a prediction table is generated for each image to be compressed using a window predictor (a window formed from surrounding pixels), which results in an optimum compression performance, for larger window size. However, since the prediction table to be generated is different for each image to be compressed, the full image must be completely stored in memory for each different image in order to generate a new prediction table; also, the generation of the prediction table and the performing of prediction on the image requires each image to be scanned twice by a window predictor (which consists of surrounding data bits), causing the amount of processing to be doubled.
In addition, since the prediction table is different for each image, the table must be transmitted from the compressor to the decompressor for each image in order to enable decompression of the image. Transmitting these excess bits, called overhead bits, seriously affects the compression performance. If the size of the window predictor increases, using more neighboring data bits in predicting the value of a particular bit, the amount of overhead bits to be transmitted also increases significantly. Therefore, it is necessary to keep the window predictor size small, which further degrades compression performance. Also, implementation of the adaptive predictor in real-time hardware is very complex and expensive.
However, a non-adaptive prediction technique can also be used to successfully compress digital data. In a non-adaptive predictive encoder, the prediction table, which is pregenerated based on a large number of sample images for a given window predictor of optimum size and shape and which is the same for all images to be compressed, is not optimum for the images, due to non-occurring states of the sample images. But since the pregenerated prediction table is stored in a permanent memory device, such as a read-only memory (ROM), at both the compressor and decompressor, no overhead bits must be transmitted, thereby improving the compression ratio. Also, since the overhead bit requirement increases as the size of the window predictor increases, a large window predictor can be used for the non-adaptive prediction technique, which results in improved compression performance when compared to the adaptive prediction technique. Also, since the same prediction table is used for all images, and no memory is needed to store the image, the hardware complexity and cost is also greatly reduced. Furthermore, the real-time compression/decompression processes will be significantly faster in the non-adaptive prediction technique than the adaptive prediction technique, since the image is scanned by the window predictor only once for performing prediction.